|
The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.〔A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", ''Computing'' 7 (1971), pp. 281–292.〕 The run-time bit complexity is, in Big O notation, O(''n'' log ''n'' log log ''n'') for two ''n''-digit numbers. The algorithm uses recursive Fast Fourier transforms in rings with 22''n'' + 1 elements, a specific type of number theoretic transform. The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007, when a new method, Fürer's algorithm, was announced with lower asymptotic complexity;〔Martin Fürer, "(Faster integer multiplication )", STOC 2007 Proceedings, pp. 57–66.〕 however, Fürer's algorithm currently only achieves an advantage for astronomically large values and is not used in practice. In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2215 to 2217 (10,000 to 40,000 decimal digits).〔Rodney Van Meter and Kohei M. Itoh, "(Fast quantum modular exponentiation )", ''Physical Review'' A, Vol. 71 (2005).〕〔(Overview of Magma V2.9 Features, arithmetic section ): Discusses practical crossover points between various algorithms.〕〔Luis Carlos Coronado García, "( Can Schönhage multiplication speed up the RSA encryption or decryption? )", ''University of Technology, Darmstadt'' (2005)〕 The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (33,000 to 150,000 decimal digits), depending on architecture.〔(【引用サイトリンク】url=http://gmplib.org/devel/MUL_FFT_THRESHOLD.html )〕 There is a Java implementation of Schönhage–Strassen which uses it above 74,000 decimal digits.〔(【引用サイトリンク】url=https://github.com/tbuktu/bigint/raw/master/src/main/java/java/math/BigInteger.java )〕 Applications of the Schönhage–Strassen algorithm include mathematical empiricism, such as the Great Internet Mersenne Prime Search and computing approximations of ''π'', as well as practical applications such as Kronecker substitution, in which multiplication of polynomials with integer coefficients can be efficiently reduced to large integer multiplication; this is used in practice by GMP-ECM for Lenstra elliptic curve factorization.〔 ==Details== This section explains in detail how Schönhage–Strassen is implemented. It is based primarily on an overview of the method by Crandall and Pomerance in their ''Prime Numbers: A Computational Perspective''.〔R. Crandall & C. Pomerance. ''Prime Numbers – A Computational Perspective''. Second Edition, Springer, 2005. Section 9.5.6: Schönhage method, p. 502. ISBN 0-387-94777-9〕 This variant differs somewhat from Schönhage's original method in that it exploits the discrete weighted transform to perform negacyclic convolutions more efficiently. Another source for detailed information is Knuth's ''The Art of Computer Programming''.〔Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2. Section 4.3.3.C: Discrete Fourier transforms, pg.305.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Schönhage–Strassen algorithm」の詳細全文を読む スポンサード リンク
|